//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
// Related Topics 字符串 回溯 👍 578 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：字符串的排列
public class ZiFuChuanDePaiLieLcof {
    public static void main(String[] args) {
        Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
        // TO TEST
        System.out.println(Arrays.toString(solution.permutation("aab")));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String[] permutation(String s) {
            // 所有得字符串排列
            if (s == null || s.length() == 0) {
                return new String[]{};
            }

            Set<String> list = new HashSet<>();
            char[] chars = s.toCharArray();
            int clen = chars.length;
            for (int i = 0; i < clen; i++) {
                // 进行交换
                char temp = chars[i];
                chars[i] = chars[0];
                chars[0] = temp;

                // 后面的子串进行操作
                permutation(chars, 1, list);

                // 进行还原
                temp = chars[0];
                chars[0] = chars[i];
                chars[i] = temp;
            }
            return list.toArray(new String[0]);
        }

        public void permutation(char[] chars, int k, Set<String> list) {
            if (k >= chars.length - 1) {
                list.add(String.valueOf(chars));
                return;
            }
            int clen = chars.length;
            for (int i = k; i < clen; i++) {
                // 进行交换
                char temp = chars[i];
                chars[i] = chars[k];
                chars[k] = temp;

                // 后面的子串进行操作
                permutation(chars, k + 1, list);

                // 进行还原
                temp = chars[k];
                chars[k] = chars[i];
                chars[i] = temp;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
